import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 438. Find All Anagrams in a String
 * 438. 找到字符串中所有字母异位词
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string
 */
class FindAllAnagramsInAString  {

    /**
     * 方法： findAnagrams
     * 逻辑: 使用定长滑动窗口，统计字符串s中所有与字符串p的字母出现次数相同的子串的起始索引。
     * Args:
     *     s (String): 输入字符串。
     *     p (String): 目标字符串，用于比较字母出现次数。
     * Returns:
     *     List<Integer>: 返回所有符合条件的子串的起始索引。
     * Time:  
     *     O(n), 其中n是字符串s的长度。
     * Space:  
     *     O(1), 固定大小的数组用于统计字母出现次数。
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int[] cntP = new int[26];
        for(char c : p.toCharArray()){
            cntP[c - 'a'] ++; //统计p每种字母出现次数
        }
        int[] cntS = new int[26]; // 统计 s 的长为 p.length() 的子串 s' 的每种字母的出现次数
        for(int right = 0; right < s.length(); right ++){
            int c = s.charAt(right) - 'a';
            cntS[c]++; //右端点字母进入窗口
            int left = right - p.length() + 1;
            if(left < 0){// 窗口长度不足 p.length()
                continue;
            }
            if(Arrays.equals(cntS, cntP)){// s' 和 p 的每种字母的出现次数都相同
                ans.add(left); // s' 左端点下标加入答案
            }
            cntS[s.charAt(left) - 'a']--;//左端点字母离开窗口
        }
        return ans;
    }


    /**
     * 方法： findAnagrams1
     * 逻辑: 使用不定长滑动窗口，统计字符串s中所有与字符串p的字母出现次数相同的子串的起始索引。
     * Args:
     *     s (String): 输入字符串。
     *     p (String): 目标字符串，用于比较字母出现次数。
     * Returns:
     *     List<Integer>: 返回所有符合条件的子串的起始索引。
     * Time:  
     *     O(n), 其中n是字符串s的长度。
     * Space:  
     *     O(1), 固定大小的数组用于统计字母出现次数。
     */
    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int[] cnt = new int[26]; //统计p每种字母出现次数
        for(char c : p.toCharArray()){
            cnt[c - 'a'] ++;
        }
        int left = 0;
        for(int right = 0; right < s.length(); right ++){
            int c = s.charAt(right) - 'a';
            cnt[c]--; //右端点字母进入窗口
            while(cnt[c] < 0){
                cnt[s.charAt(left) - 'a']++; //左端点字母离开窗口
                left++;
            }
            // s' 和 p 的每种字母的出现次数都相同
            if(right - left + 1 == p.length()){
                ans.add(left); // s' 左端点下标加入答案
            }
        }
        return ans;
    }
}